#include <stdio.h>
#undef assert
#define assert(X) {if(!(X)){printf("assertion failed on line %d\n >>%s\n", __LINE__, #X);++*((int*)(NULL));}}
#define inline 

const int inf = 100000000;

#define maxSize 1000000

inline static int ABS(int x){return x>=0?x:-x;}

struct posIterator{
    int *arts;
    short *poss;
    int artI, posI;
    int posSiz, artSiz;
    int art, pos;
    int offset;
    int fromIndex;
};

typedef struct posIterator posIterator;

inline static void reset ( posIterator *iter ){
    iter->artI = iter->posI = 0;
    if ( iter->arts != NULL ) iter->art = ABS(iter->arts[iter->artI]);
    else iter->art = inf;
    if ( iter->poss != NULL ) iter->pos = ABS(iter->poss[iter->posI]);
    else iter->pos = 0;
}

inline static int end ( posIterator *iter ){
    if ( iter->posI >= iter->posSiz ) return 1;
    if ( iter->artI >= iter->artSiz ) return 1;
    return 0;
}

inline static void inc ( posIterator *iter ){
    assert ( !end ( iter ) );
    
    iter->posI++;
    if ( iter->posI == iter->posSiz ) iter->art = inf;
    else if ( iter->poss[iter->posI] < 0 ){
        iter->artI++;
        iter->art = iter->arts[iter->artI];
        iter->pos = - iter->poss[iter->posI];
    }
    else {
        iter->pos = iter->poss[iter->posI];
    }
}

inline static int less ( posIterator *iterA, posIterator *iterB ){
    if ( iterA->art != iterB->art ) return iterA->art < iterB->art;
    return iterA->pos - iterA->offset < iterB->pos - iterB->offset;
}

inline static int eq ( posIterator *iterA, posIterator *iterB ){
    return iterA->art == iterB->art && iterA->pos - iterA->offset == iterB->pos - iterB->offset;
}

inline static void writeit ( posIterator *iter, int article, int position ){
//    assert (position > 0)
    if ( iter->posI >= maxSize || iter->artI >= maxSize ) return; //< bleeee
    
    position = ABS ( position );
    if ( article == iter->art ){
        iter->poss[iter->posI++] = position;
    }
    else {
        iter->art = article;
        iter->arts[iter->artI++] = article;
        iter->poss[iter->posI++] = -position;
    }
    assert (iter->posI <= maxSize && writeit);
    assert (iter->artI <= maxSize && writeit);
}


/// A, B -> listy wejściowe, C lista wyjściowa 
static void _andPositions( posIterator *itA, posIterator *itB, posIterator *itC ){
    
    while ( !end( itA ) && !end( itB ) ){
        if ( eq( itA, itB ) ){
            writeit ( itC, itA->art, itA->pos - itA->offset );
            inc ( itA );
            inc ( itB );
        }
        if ( less ( itA, itB ) ) inc ( itA );
        if ( less ( itB, itA ) ) inc ( itB );
    }
}

/// A, B -> listy wejściowe, C lista wyjściowa 
static void _orPositions( posIterator *itA, posIterator *itB, posIterator *itC ){
    
    while ( !end(itA) || !end(itB) ){
        if ( eq ( itA, itB) ){
            writeit ( itC, itA->art, itA->pos - itA->offset );
            inc ( itA );
            inc ( itB );
        } 
        else if ( less ( itA, itB ) ){
            writeit ( itC, itA->art, itA->pos - itA->offset );
            inc ( itA );
        }
        else if ( less ( itB, itA ) ){
            writeit ( itC, itB->art, itB->pos - itB->offset );
            inc ( itB );
        }
        else assert ( 0 );
    }
}


/// A, B --> C
static void _andArticles ( posIterator *argA, posIterator *argB, posIterator *argC  ){
  
  int *LA = argA->arts; int lenA = argA->artSiz;
  int *LB = argB->arts; int lenB = argB->artSiz;
  int *LC = argC->arts;
  int ia = 0;
  int ib = 0;
  int ic = 0;

  while ( ia < lenA && ib < lenB ){
    if ( LA[ia] < LB[ib] ) ++ia;
    else if ( LA[ia] > LB[ib] ) ++ib;
    else {
      LC[ic++] = LA[ia];
      ++ia, ++ib;
    }
  }
  argC->artI = ic;
}


/// A, B --> C
static void _orArticles ( posIterator *argA, posIterator *argB, posIterator *argC  ){
  
  int *LA = argA->arts; int lenA = argA->artSiz;
  int *LB = argB->arts; int lenB = argB->artSiz;
  int *LC = argC->arts;
  int ia = 0;
  int ib = 0;
  int ic = 0;
  
  while ( ia < lenA || ib < lenB ){
    if ( ia == lenA ) LC[ic++] = LB[ib++];
    else if ( ib == lenB  ) LC[ic++] = LA[ia++];
    else if ( (ib == lenB  ) || (  LA[ia] < LB[ib] ) ) LC[ic++] = LA[ia++];
    else if ( ia == lenA || LA[ia] > LB[ib] ) LC[ic++] = LB[ib++];
    else {
      LC[ic++] = LA[ia];
      ++ia, ++ib;
    }
  }
  argC->artI = ic;
}




#include <Python.h>
posIterator iter1, iter2, iter3;


static int PythonReadArgs ( PyObject* args ){
    iter2.offset = 0;
    if (!PyArg_ParseTuple(args, "(iiiii)(iiiii)|i",
        &iter1.arts,
        &iter1.artSiz,
        &iter1.poss,
        &iter1.posSiz,
        &iter1.fromIndex,
        &iter2.arts,
        &iter2.artSiz,
        &iter2.poss,
        &iter2.posSiz,
        &iter2.fromIndex,
        &iter2.offset
         )
        ) return 0;
//    assert ( iter1.artSiz < maxSize );
//    assert ( iter2.artSiz < maxSize );
//    assert ( iter1.posSiz < maxSize );
//    assert ( iter2.posSiz < maxSize );
    if ( iter1.artSiz >= maxSize ) iter1.artSiz = maxSize - 1;
    if ( iter1.posSiz >= maxSize ) iter1.posSiz= maxSize - 1;
    if ( iter2.artSiz >= maxSize ) iter2.artSiz = maxSize - 1;
    if ( iter2.posSiz >= maxSize ) iter2.posSiz = maxSize - 1;
    
    
    iter3.arts = malloc ( maxSize * sizeof ( int )  );
    iter3.poss = malloc ( maxSize * sizeof ( int )  );
    assert ( iter3.arts != NULL && "Nie mozna przydzielic pamieci" );
    assert ( iter3.poss != NULL && "Nie mozna przydzielic pamieci" );
    reset ( &iter1 );
    reset ( &iter2 );
    reset ( &iter3 );
    iter3.art = -1;
    return 1;
}

static PyObject* PythonCreateList ( int *from, int len){
    assert (len < maxSize);
PyObject* list = PyList_New( len );
    int i;
    for( i = 0 ; i < len; i++){
        PyList_SetItem(list, i, PyLong_FromLong( from[i] ) );
    }
    return list;
}

static PyObject* returnPython () {
    if ( !iter1.fromIndex ){
        free ( iter1.arts );
        free ( iter1.poss );
    }
    if ( !iter2.fromIndex ){
        free ( iter2.arts );
        free ( iter2.poss );
    }
    return Py_BuildValue("(iiiii)", iter3.arts, iter3.artI, iter3.poss, iter3.posI, 0 );
}


static PyObject* andArticles (PyObject* self, PyObject* args){
    if ( !PythonReadArgs ( args ) ) return NULL;
    _andArticles( &iter1, &iter2, &iter3 );
    return returnPython ();
}

static PyObject* orArticles (PyObject* self, PyObject* args){
    if ( !PythonReadArgs ( args ) ) return NULL;
    _orArticles( &iter1, &iter2, &iter3 );
    return returnPython ();
}

static PyObject* andPositions (PyObject* self, PyObject* args){
    if ( !PythonReadArgs ( args ) ) return NULL;
    _andPositions ( &iter1, &iter2, &iter3 );
    return returnPython ();
}

static PyObject* orPositions (PyObject* self, PyObject* args){
    if ( !PythonReadArgs ( args ) ) return NULL;
    _orPositions ( &iter1, &iter2, &iter3 );
    return returnPython ();
}

static PyObject* getArticles ( PyObject* self, PyObject* args ){
    int *tab;
    short *tab2;
    int siz;
    int fromIndex;
    int dummy;
    if (!PyArg_ParseTuple(args, "(iiiii)",
        &tab,
        &siz,
        &tab2,
        &dummy,
        &fromIndex
         )) return NULL;
    PyObject *ret = PythonCreateList ( tab, siz );
    if ( !fromIndex ){
        free ( tab );
        free ( tab2 );
    }
    return ret;
}

static PyObject* freeMem(PyObject* self, PyObject* args)
{
    int l1, len1, l2, len2,freeable;
    if (!PyArg_ParseTuple(args, "(iiiii)", &l1, &len1, &l2, &len2, &freeable))
        return NULL;
    int* list1 = (int *) l1;
    short * list2 = (short*) l2;
    
    if( ! freeable ){
        free(list1);
        free(list2);
    }
    
    return Py_BuildValue("i",  0 ) ;  ;
}


static PyMethodDef HelloMethods[] =
{
     {"andPositions", andPositions, METH_VARARGS, " "},
     {"orPositions", orPositions, METH_VARARGS, " "},
     {"andArticles", andArticles, METH_VARARGS, " "},
     {"orArticles", orArticles, METH_VARARGS, " "},
     {"getArticles", getArticles, METH_VARARGS, " "},
     {"free", freeMem, METH_VARARGS, " "},     
     {NULL, NULL, 0, NULL}
};
 
PyMODINIT_FUNC initrapidUtils(void)
{
     (void) Py_InitModule("rapidUtils", HelloMethods);
}
